This invention relates to the field of data processing systems. More particularly, this invention relates to the arbitration between input signals in order to select an output signal.
It is known to provide data processing systems in which it is necessary to arbitrate between multiple input signals in order to select an output signal. As an example, within a system-on-chip integrated circuit such as that illustrated in FIG. 1 of the accompanying drawings, there may be provided multiple transaction masters 2, 4 connected via interconnect circuitry 6 to multiple transaction slaves 8, 10, 12, 14. Each of the transaction masters 2, 4, may generate one or more transactions which are routed via the interconnect circuitry 6 to a target transaction slave 8, 10, 12, 14. Each of these transactions may have a priority value (e.g. representing a quality of service required for that transaction) associated with it and which may be used to control any arbitration that is necessary. A given transaction master 2, 4 may generate more than one stream of transactions. These transactions may have different priority values associated with them.
If a plurality of transactions are directed toward a given transaction slave 8, 10, 12, 14, then a bottleneck can arise in which multiple transactions will seek to pass through the same resources within the interconnect circuitry 6 at the same time to reach the desired transaction slave 8, 10, 12, 14. In these circumstances, it is necessary to arbitrate between the conflicting transactions (which represent a plurality of inputs) in order to select which of the transactions is to be passed onward to the target slave 8, 10, 12, 14 (i.e. which should be selected as the output). The priority values associated with each of the transactions (inputs) may be compared and the transaction with the highest priority as indicated by its priority value may be selected to be passed onward at that time. The remaining transactions may be buffered and passed later.
A problem that arises in such systems is that the comparison of the priority values necessary to perform arbitration may constrain the maximum speed at which transactions may be passed through the interconnect circuitry 6. The comparison to perform arbitration may effectively become the critical path at the point at which the arbitration is required. This problem becomes worse when mechanisms are added to deal with tie-break situations in which multiple inputs have priority values indicating the same level of priority. When such tie-break situations arise, it is important that they are dealt with a controlled manner so that a given input is not starved of the ability to be selected as the output. As inputs of the same level of priority clash, it is important that the tie break mechanisms should be “fair” in how they select the output such that each input is selected sufficiently frequently not to result in erroneous behaviour, e.g. one input is starved.
While tie-break mechanisms are important as described above, a problem arises in that they can add additional level of comparison that needs to be performed and accordingly can further constrain the maximum throughput. A comparison of the priority values which accompany an input, which is then followed by a mechanism to deal with any tie-break that is needed can extend the critical path and slow down the processing to an undesirable degree.